package com.sjf.day03.avl;

import cn.hutool.core.util.ObjectUtil;


/**
 * 平衡二叉树
 *
 * @author <huangtang>
 * @since 2022/1/11 14:14
 **/
public class AVLTreeDemo {

    public static void main(String[] args) {
        //int[] arr = {7,3,10,12,5,1,9,2,15,16,17,18};
        //int[] arr = {10,12,8,9,7,6};
        int[] arr = {10,11,8,9,7,6};
        AVLTree avlTree = new AVLTree();
        for (int j : arr) {
            avlTree.add(new Node2(j));
        }
        avlTree.midOrder();
        System.out.println("树的高度："+avlTree.root.height());
        System.out.println("左子树的高度："+avlTree.leftHeight());
        System.out.println("右子树的高度："+avlTree.rightHeight());
        avlTree.midOrder();
        System.out.println("根节点为："+avlTree.root);
    }

}



/**
 * 平衡二叉树
 */
class AVLTree{
    Node2 root; //头节点

    public int leftHeight(){
        return root.leftHeight();
    }

    public int rightHeight(){
        return root.rightHeight();
    }


    /**
     * 删除节点
     * @param val 删除节点的val
     */
    public void delNode(int val){
        if(root == null){
            return;
        }else{
            //找到删除的节点
            Node2 targetNode = search(val);
            if(ObjectUtil.isNull(targetNode)){
                return;
            }

            if(ObjectUtil.isNull(root.left) && ObjectUtil.isNull(root.right)){
                //删除的树中只有一个节点
                root = null;
                return;
            }

            //去找到targetNode的父节点
            Node2 parent = searchParent(val);

            //删除的节点是叶子节点
            if(targetNode.left == null && targetNode.right == null ){
                if(parent.left!=null && parent.left.val == targetNode.val){
                    parent.left = null;
                }else if(parent.right!=null && parent.right.val == targetNode.val){
                    parent.right = null;
                }
            }else if(targetNode.left!=null && targetNode.right!=null){
                //删除有两颗子树的节点
                targetNode.val = delRightTreeMin(targetNode.right);
                //targetNode.val = delLeftTreeMax(targetNode.left);
            }else{
                //删除只有一棵子树的节点
                if(targetNode.left!=null){
                    if(parent == null){
                        root = root.left;
                        return;
                    }
                    //子树在左边
                    if(parent.left.val == val){
                        //如果targetNode是parent的左子节点
                        parent.left = targetNode.left;
                    }else{
                        //如果targetNode是parent的右子节点
                        parent.right = targetNode.left;
                    }
                }else{
                    if(parent == null){
                        root = root.right;
                        return;
                    }
                    //子树在右边
                    if(parent.right.val == val){
                        parent.right = targetNode.right;
                    }else{
                        parent.left = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 找到右子树的最小节点返回并删除
     * @param node 传入的节点为当前节点
     * @return 返回最小节点对应的val
     */
    public int delRightTreeMin(Node2 node){
        Node2 temp = node;
        //循环查找左节点，直到最小的找到
        while(temp.left != null){
            temp = temp.left;
        }
        delNode(temp.val); //删除最小节点
        return temp.val;
    }

    /**
     * 找到左子树的最大节点返回并删除
     * @param node 传入的节点为当前接地爱你
     * @return 返回最大节点对应的val
     */
    public int delLeftTreeMax(Node2 node){
        Node2 temp = node;
        while(temp.right!=null){
            temp = temp.right;
        }
        delNode(temp.val);
        return temp.val;

    }

    //查找要删除的节点
    public Node2 search(int val){
        if(root == null){
            return null;
        }else{
            return root.search(val);
        }
    }

    //查找父节点
    public Node2 searchParent(int val){
        if(root==null){
            return null;
        }else{
            return root.searchParent(val);
        }
    }


    /**
     * 添加节点
     * @param node 要添加的节点
     */
    public void add(Node2 node){
        if(root == null){
            root = node;
        }else{
            root.add(node);
        }

    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(root == null){
            System.out.println("树为空，无法中序遍历");
        }else{
            root.midOrder();
        }
    }
}



/**
 * 创建树节点
 */
class Node2{
    int val;
    Node2 left;
    Node2 right;

    //右旋转
    public void rightRotate(){
        Node2 newNode = new Node2(this.val);
        newNode.right = this.right;
        newNode.left = this.left.right;
        this.val = this.left.val;
        this.left = this.left.left;
        this.right = newNode;
    }

    //左旋转
    public void leftRotate(){
        //创建新的节点
        Node2 newNode = new Node2(this.val);
        //把新的节点的左子树置为当前节点的左子树
        newNode.left = this.left;
        //把新的节点的右子树置为当前节点的右子树的左子树
        newNode.right = this.right.left;
        //把当前节点的值替换成右子节点的值
        this.val = this.right.val;
        //把当前节点的右子树置为当前节点的右子树的右子树
        this.right = this.right.right;
        //把当前节点的左子节点置为新的节点
        this.left = newNode;
    }

    //返回左子树的高度
    public int leftHeight(){
        if(left == null){
            return 0;
        }
        return left.height();
    }
    //返回右子树的高度
    public int rightHeight(){
        if(right == null){
            return 0;
        }
        return right.height();
    }

    //返回以当前节点为根节点的树的高度
    public int height(){
        return Math.max(left == null ? 0:left.height(),right == null ? 0: right.height()) + 1;
    }

    public Node2(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node2{" +
                "val=" + val +
                '}';
    }

    /**
     *  查找要删除的节点
     * @param val 要删除节点的值
     * @return 返回要删除的节点对象
     */
    public Node2 search(int val){
        if(this.val == val) {
            return this;
        }else if(val < this.val){
            //递归左子树
            if(this.left == null){
                return null;
            }
            return this.left.search(val);
        }else {
            //递归右子树
            if(this.right == null){
                return null;
            }
            return this.right.search(val);
        }
    }

    /**
     * 查找要删除节点的父节点
     * @param val 查找节点的值
     * @return 删除节点的父节点
     */
    public Node2 searchParent(int val){
        if((this.left!=null && this.left.val == val) || (this.right!=null && this.right.val == val)){
            return this;
        }else {
            //如果查找的值小于当前节点,并且当前节点的左子节点不为空
            if(val < this.val && this.left!=null){
                return this.left.searchParent(val); //递归左子树查找
            }else if(val >= this.val && this.right!=null){
                return this.right.searchParent(val); //递归右子树查找
            }else{
                return null;//没有父节点
            }
        }
    }

    /**
     * 添加节点
     * @param Node2 需要添加的节点
     */
    public void add(Node2 Node2){
        if(Node2 == null ) return;

        if(Node2.val < this.val){
            if(this.left == null){
                this.left = Node2;
            }else{
                this.left.add(Node2);
            }
        }else if(Node2.val > this.val){
            if(this.right == null) {
                this.right = Node2;
            }else{
                this.right.add(Node2);
            }
        }else {
            if(this.right == null){
                this.right = Node2;
            }else{
                this.right.add(Node2);
            }
        }

        //当添加完壹个节点后，右子树 - 左子树 > 1 就左旋转
        if (rightHeight() - leftHeight() > 1){
            //如果当前节点的右子树的左子树高度大于当前节点的左子树高度
            if(this.right!=null && this.right.leftHeight() > this.rightHeight()){
                //先对当前节点的右子树进行右旋转
                this.right.rightRotate();
                //再对当前节点进行左旋转
            }
            //直接进行左旋转
           this.leftRotate();
            return ; //防止下面的操作继续旋转
        }
        //左子树 - 右子树 > 1 就右旋转
        if(leftHeight() - rightHeight() > 1){
            //如果当前节点的左子树的右子树的高度大于当前节点的右子树高度
            if(this.left!=null && this.left.rightHeight() > this.rightHeight()){
                //先对当前节点的左子树进行左旋转
                this.left.leftRotate();
                //再对当前节点进行右旋转
            }
            //直接进行右旋转
            this.rightRotate();
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder(){
        if(this.left!=null){
            this.left.midOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.midOrder();
        }
    }
}